type Position = (usize, usize);
pub fn solve_maze(maze: Vec<Vec<char>>, start: Position, end: Position) -> Vec<Position> {
    let layout = maze;
    let maze = Maze::new(&layout, start, end);
    Solver::new(&maze).solve()
}
struct Solver<'a> {
    remaining: Vec<MazePathState<'a>>,
    solution: Option<Vec<Position>>,
}
impl<'a> Solver<'a> {
    pub fn new(maze: &'a Maze<'a>) -> Self {
        let remaining = vec![MazePathState::new(maze)];
        Self {
            remaining,
            solution: None,
        }
    }
    pub fn solve(mut self) -> Vec<Position> {
        loop {
            match self.remaining.pop() {
                None => {
                    return match self.solution {
                        Some(x) => x,
                        None => vec![],
                    };
                }
                Some(state) => {
                    self.process_step(state.clone(), Direction::Left);
                    self.process_step(state.clone(), Direction::Right);
                    self.process_step(state.clone(), Direction::Up);
                    self.process_step(state, Direction::Down);
                }
            }
        }
    }
    fn process_step(&mut self, state: MazePathState<'a>, dir: Direction) {
        use MazeWalkResult::*;
        match state.walk(dir) {
            Wall | OutOfBounds | AlreadyVisited => {}
            Path(state) => self.remaining.push(state),
            Exit(solution) => {
                if self.solution.is_none() || solution.len() < self.solution.as_ref().unwrap().len()
                {
                    self.solution = Some(solution);
                }
            }
        }
    }
}
#[derive(Copy, Clone, Eq, PartialEq)]
enum Direction {
    Left,
    Right,
    Up,
    Down,
}
enum MazeWalkResult<'a> {
    Wall,
    OutOfBounds,
    AlreadyVisited,
    Exit(Vec<Position>),
    Path(MazePathState<'a>),
}
struct Maze<'a> {
    data: &'a Vec<Vec<char>>,
    start: Position,
    end: Position,
    height: usize,
    width: usize,
}
impl<'a> Maze<'a> {
    pub fn new(data: &'a Vec<Vec<char>>, start: (usize, usize), end: (usize, usize)) -> Self {
        // TODO: validate maze dimensions and positions
        let height = data.len();
        if height == 0 {
            panic!("height must be greater than zero.");
        }
        let width = data[0].len();
        if width == 0 {
            panic!("width must be greater than zero.");
        }
        for row in data {
            if row.len() != width {
                panic!("width must consistent across rows.");
            }
        }
        assert_eq!(data[start.0][start.1], 'S');
        assert_eq!(data[end.0][end.1], 'E');
        Self {
            data,
            start,
            end,
            height,
            width,
        }
    }
}
#[derive(Clone)]
struct MazePathState<'a> {
    maze: &'a Maze<'a>,
    path: Vec<Position>,
}
impl<'a> MazePathState<'a> {
    pub fn new(maze: &'a Maze<'a>) -> Self {
        Self {
            maze,
            path: vec![maze.start],
        }
    }
    pub fn walk(mut self, dir: Direction) -> MazeWalkResult<'a> {
        let Some(current) = self.move_pos(self.get_current_pos(), dir) else {
            return MazeWalkResult::OutOfBounds;
        };
        if self.path.iter().filter(|&&x| x == current).next().is_some() {
            return MazeWalkResult::AlreadyVisited;
        }
        self.path.push(current);
        match self.maze.data[current.0][current.1] {
            'E' => MazeWalkResult::Exit(self.path),
            '#' => MazeWalkResult::Wall,
            '.' => MazeWalkResult::Path(self),
            _ => panic!("Unhandled strange case"),
        }
    }
    fn get_current_pos(&self) -> Position {
        *self.path.last().unwrap()
    }
    fn move_pos(&self, mut pos: Position, dir: Direction) -> Option<Position> {
        match dir {
            Direction::Right => pos.1 += 1,
            Direction::Down => pos.0 += 1,
            Direction::Left => {
                if pos.1 == 0 {
                    return None;
                }
                pos.1 -= 1;
            }
            Direction::Up => {
                if pos.0 == 0 {
                    return None;
                }
                pos.0 -= 1;
            }
        }
        if pos.0 >= self.maze.height || pos.1 >= self.maze.width {
            None
        } else {
            Some(pos)
        }
    }
}
